// 快速选择算法
function quickSelect(arr, left, right, k) {
    if (left === right) {
        return arr[left];
    }

    const pivotIndex = partition(arr, left, right);

    if (k === pivotIndex) {
        return arr[k];
    } else if (k < pivotIndex) {
        return quickSelect(arr, left, pivotIndex - 1, k);
    } else {
        return quickSelect(arr, pivotIndex + 1, right, k);
    }
}

// 分区函数
function partition(arr, left, right) {
    const pivot = arr[right]; // 选择右端的元素作为基准
    let i = left;
    for (let j = left; j < right; j++) {
        if (arr[j] <= pivot) {
            [arr[i], arr[j]] = [arr[j], arr[i]]; // 交换小于基准的元素
            i++;
        }
    }
    [arr[i], arr[right]] = [arr[right], arr[i]]; // 把基准元素放到正确位置
    return i;
}

// 生成不重复的随机数数组
function generateUniqueRandomArray(size, min, max) {
    const uniqueNumbers = new Set();
    while (uniqueNumbers.size < size) {
        const randomNumber = Math.floor(Math.random() * (max - min + 1)) + min;
        uniqueNumbers.add(randomNumber);
    }
    return Array.from(uniqueNumbers);
}

// 使用示例
const dataSize = 10000; // 数据规模
const min = 1;          // 最小值
const max = 100000;     // 最大值，确保生成的随机数分布广泛

// 开始计时
console.time("Execution Time");

// 生成数据
const arr = generateUniqueRandomArray(dataSize, min, max);

// 查找第 k 小的元素
const k = 5000; // 查找第5001小的元素（索引从0开始）
const result = quickSelect(arr, 0, arr.length - 1, k);

// 输出结果
console.log(`第${k + 1}小的元素是: ${result}`);

// 结束计时并输出花费时间
console.timeEnd("Execution Time");
